package Leetcode第二期;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : K k
 * @date : 11:10 2020/9/24
 * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
 *
 * 示例 1:
 *
 * 输入: n = 12
 * 输出: 3
 * 解释: 12 = 4 + 4 + 4.
 * 示例 2:
 *
 * 输入: n = 13
 * 输出: 2
 * 解释: 13 = 4 + 9.
 */
public class 完全平方数_279 {
    int min=Integer.MAX_VALUE;
    //思路1：DFS超出时间限制 不推荐
    public int numSquares(int n) {
        int num=1;
        //找小于n的完全平方数
        for(int i=1;i<=n;i++){
            if(i*i>n){
                num=i-1;
                break;
            }
        }
        List<Integer> res=new ArrayList<>();
        dfsSolver(num,n,res);

        return min;
    }

    private void dfsSolver(int num, int n, List<Integer> res) {
        if(n==0){
            min=Math.min(min,res.size());
            System.out.println(res);
            return;
        }else if(n<0){
            return;
        }
        for(int i=num;i>=1;i--){
            res.add(i*i);
            dfsSolver(num,n-i*i,res);
            res.remove(res.size()-1);
        }
    }

    //思路二：动态规划
    public int numSquaresA(int n) {
        int[] dp = new int[n + 1]; // 默认初始化值都为0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最坏的情况就是每次+1
            for (int j = 1; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        完全平方数_279 x=new 完全平方数_279();
        System.out.println(x.numSquaresA(12));
    }
}
